/*************************************************************************
 * File Name:    Unique_Binary_Search_Trees_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 02 Nov 2013 05:26:44 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Unique Binary Search Trees II
 | Given n, generate all structurally unique BST's (binary search trees)
 | that store values 1...n.
 |
 | For example,
 | Given n = 3, your program should return all 5 unique BST's shown below.
 |
 |    1         3     3      2      1
 |     \       /     /      / \      \
 |      3     2     1      1   3      2
 |     /     /       \                 \
 |    2     1         2                 3
 | confused what "{1,#,2,3}" means? > read more on how binary tree is
 | serialized on OJ.
 |
 | OJ's Binary Tree Serialization:
 | The serialization of a binary tree follows a level order traversal,
 | where '#' signifies a path terminator where no node exists below.
 |
 | Here's an example:
 |
 |       1
 |      / \
 |     2   3
 |         /
 |        4
 |         \
 |          5
 | The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        if (n == 0) return vector<TreeNode*>(1, (TreeNode*)NULL);
        vector<TreeNode *> ans;
        
        for (int i = 1; i <= n; ++i) {
            vector<TreeNode *> subtree = createSubTree(1, i, n);
            ans.insert(ans.end(), subtree.begin(), subtree.end());
        }
        return ans;
    }
    
    vector<TreeNode *> createSubTree(int left, int root, int right)
    {
        if (left > right) return vector<TreeNode*>(1, (TreeNode*)NULL);
        
        vector<TreeNode *> leftTree, rightTree;
        
        for (int i = left; i < root; ++i) {
            vector<TreeNode*> t = createSubTree(left, i, root - 1);
            leftTree.insert(leftTree.end(), t.begin(), t.end());
        }
        for (int i = root + 1; i <= right; ++i) {
            vector<TreeNode*> t = createSubTree(root + 1, i, right);
            rightTree.insert(rightTree.end(), t.begin(), t.end());
        }
        if (leftTree.size() == 0) leftTree.push_back(NULL);
        if (rightTree.size() == 0) rightTree.push_back(NULL);
        
        vector<TreeNode *> ret;
        
        for (size_t i = 0; i < leftTree.size(); ++i) {
            for (size_t j = 0; j < rightTree.size(); ++j) {
                TreeNode *tree = new TreeNode(root);
                tree->left = leftTree[i];
                tree->right = rightTree[j];
                ret.push_back(tree);
            }
        }
        if (ret.size() == 0) ret.push_back(NULL);
        return ret;
    }
};

int
main(int argc, char *argv[])
{
    Solution sol;

    sol.generateTrees(3);

    return 0;
}
